package com.copa.l200;

/**
 * @author copa
 * @createDate 2022-05-23 09:42
 * @function 并查集「Union Find」法
 */
public class Test3 {

    public int numIslands(char[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        // 这个为水地的标记数
        int waters = 0;
        // 初始化一维数组
        UnionFind unionFind = new UnionFind(grid);
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '0') {
                    // 如果为水地则增加waters
                    waters++;
                } else {
                    // 如果为陆地，则按上下左右进行是否合并的操作，若可以合并则合并
                    int[][] directions = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
                    for (int[] direction : directions) {
                        int x = i + direction[0];
                        int y = j + direction[1];
                        if (x >= 0 && y >= 0 && x < row && y < col && grid[x][y] == '1') {
                            // 符合条件就合并
                            unionFind.union(x * col + y, i * col + j);
                        }
                    }
                }
            }
        }
        // 合并后剩余个数 - 水地数
        return unionFind.getCount() - waters;
    }

    public static void main(String[] args) {
        char[][] grid = new char[][]{
                {'1','1','0','0','0'},
                {'1','1','0','0','0'},
                {'0','0','1','0','0'},
                {'0','0','0','1','1'}
        };
        System.out.println(new Test3().numIslands(grid));
    }
}

class UnionFind {
    // grid转为一维数组
    private int[] root = null;
    // 合并后实际个数
    private int count = 0;

    /**
     * 将二维数组转换为一位数组 char[x][y] -> int[x * y]
     * @param grid 传进来的网格
     */
    public UnionFind(char[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        count = row * col;
        root = new int[row * col];
        for (int i = 0; i < row * col; i++) {
            root[i] = i;
        }
    }

    // 寻找祖先
    public int find(int x) {
        if (x == root[x]) {
            // 如果该结点等于它自身就是父节点
            return x;
        }
        // 如果不一样就按照这个值的index去找父节点，比如说root[14]=8 ，那么继续找root[8]是不是root[8]=8
        return find(root[x]);
    }

    // 合并两个元素，使其成为共同的祖先
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            // 如果二者父节点不相等，则需要合并
            root[rootX] = rootY;
            // 合并后减去总节点
            count--;
        }
    }

    public int getCount() {
        return count;
    }

}